package com.example.nirvana.dataStructure.algorithm;

import java.util.HashMap;
import java.util.Map;

/**
 * Two Sum 问题
 * 给你一个数组和一个整数target，可以保证数组中存在两个数的和为target，请你返回这两个数的索引
 * 比如输入nums = [3,1,3,6],target = 6，算法应该返回数组[0,2]，因为 3 + 3 = 6
 */
public class TwoSum {
    /**
     * 穷举解法
     * 时间复杂度O(N^2)，空间复杂度O(1)
     *
     * @param nums 数组
     * @param target 目标数
     * @return 索引数组
     */
    int[] towSum0(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i+1; j < nums.length-i; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[] {i, j};
                }
            }
        }
        //不存在这两个数
        return new int[] {-1, -1};
    }

    /**
     * 利用哈希表解法
     * 时间复杂度O(N)，空间复杂度O(N)
     *
     * @param nums 数组
     * @param target 目标数
     * @return 索引数组
     */
    int[] towSum1(int[] nums, int target) {
        Map<Integer, Integer> index = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            index.put(num, i);
        }
        for (int i = 0; i < nums.length; i++) {
            int other = target - nums[i];
            if (index.containsKey(other) && index.get(other) != i) {
                return new int[] {i, index.get(other)};
            }
        }
        //不存在这两个数
        return new int[] {-1, -1};
    }

    /**
     * 利用双指针解法（前提是数组是有序的）
     *
     * @param nums 数组
     * @param target 目标数
     * @return 索引数组
     */
    int[] towSum2(int[] nums, int target) {
        int left = 0, right = nums.length-1;
        while(left < right) {
            int sum = nums[left] + nums[right];
            if (target == sum) {
                return new int[] {left, right};
            }else if (sum < target) {
                left++; // 让 sum 大一点
            } else {
                right--; // 让 sum 小一点
            }
        }
        //不存在这两个数
        return new int[] {-1, -1};
    }

    Map<Integer, Integer> freq = new HashMap<>();

    /**
     * 向数据结构中添加一个数 number
     * 时间复杂度O(1)
     *
     * @param number
     */
    public void add(int number) {
        // 记录number出现的次数
        freq.put(number, freq.getOrDefault(number, 0) + 1);
    }

    /**
     * 寻找当前数据结构中是否存在两个数的和为 value
     * 时间复杂度O(N)
     * @param value
     * @return
     */
    public boolean find(int value) {
        for (Integer key : freq.keySet()) {
            int other = value - key;
            // 情况一：如果连续 add 了 [3,2,3,5]，那么freq是{3:2,2:1,5:1}，执行find(6)，由于 3 出现了两次，3 + 3 = 6，所以返回 true
            if (other == key && freq.get(key) > 1) {
                return true;
            }
            // 情况二：freq是{3:2,2:1,5:1}，执行find(7)，那么key为 2，other为 5 时算法可以返回 true
            if (other != key && freq.containsKey(other)) {
                return true;
            }
        }
        return false;
    }


}
